﻿#region [ License information          ]
/* ************************************************************
 *
 * Copyright (c) Bjørn Bouet Smith, 2010, 2011
 *
 * This source code is subject to terms and conditions of 
 * Microsoft Public License (Ms-PL).
 * 
 * A copy of the license can be found in the license.txt
 * file at the root of this distribution. If you can not 
 * locate the License, please send an email to bjornsmith@gmail.com
 * 
 * By using this source code in any fashion, you are 
 * agreeing to be bound by the terms of the Microsoft 
 * Permissive License.
 *
 * You must not remove this notice, or any other, from this
 * software.
 *
 * ************************************************************/
#endregion

using System;
using System.Collections.Generic;
using System.Text;
using Smith.AMC.Collections;

namespace Smith.AMC.Network
{
    /// <summary>
    /// This class is a locator class that assists in finding the correct memcached server for a given cache key.
    /// The class uses consistent hashing to facilitate easier adding/removeing of servers without
    /// losing the entire cache cluster because of all keys will hit different servers.
    /// see http://www8.org/w8-papers/2a-webserver/caching/paper2.html for more descriptions
    /// </summary>
    public class ServerLocator
    {
        /// <summary>
        /// The number of times we should place each server node on the virtual wheel
        /// </summary>
        private const int ServerPermutations = 100;
        
        /// <summary>
        /// All the hash values for the servers
        /// </summary>
        private readonly uint[] allKeys;

        /// <summary>
        /// A dictionary that contains the server node that matches the given hash key
        /// </summary>
        private readonly SortedDictionary<uint, IMemcachedServerNode> serverKeys = new SortedDictionary<uint, IMemcachedServerNode>();
        
        /// <summary>
        /// The index of the last key in the allKeys array.
        /// </summary>
        private readonly int lastKeyIndex;

        /// <summary>
        /// The length of the allKeys array.
        /// </summary>
        private readonly int allKeysLength;
        
        /// <summary>
        /// Initializes a new instance of the <see cref="ServerLocator"/> class.
        /// </summary>
        /// <param name="servers">The servers.</param>
        public ServerLocator(IList<IMemcachedServerNode> servers)
        {
            allKeys = new uint[servers.Count * ServerPermutations];

            // Generate keys for each server
            for (int x = 0; x < servers.Count; x++)
            {
                GenerateKeys(servers[x], x);
            }

            allKeysLength = allKeys.Length;
            lastKeyIndex = allKeysLength - 1;
            Array.Sort(allKeys);
        }

        /// <summary>
        /// Locates a MemcachedServer for the given cache key
        /// </summary>
        /// <param name="cacheKey">The cache key.</param>
        /// <returns>The memcached server that matches the key</returns>
        public IMemcachedServerNode LocateServer(string cacheKey)
        {
            uint key = new Jenkins96().ComputeHash(Encoding.UTF8.GetBytes(cacheKey));

            int keyIndex = Array.BinarySearch(allKeys, key);

            // No exact match was found
            if (keyIndex < 0)
            {
                // Use the bitwise complement, i.e. nearest that match
                keyIndex = ~keyIndex;

                if (keyIndex == 0)
                {
                    keyIndex = lastKeyIndex;
                }
                else
                {
                    if (keyIndex >= allKeysLength)
                    {
                        keyIndex = 0;
                    }
                }
            }

            if (keyIndex > lastKeyIndex)
            {
                throw new InvalidOperationException(string.Format("Invalid index calculated: {0}, max value is: {1}", keyIndex, allKeys.Length - 1));
            }

            uint serverKey = allKeys[keyIndex];

            IMemcachedServerNode serverNode;
            if (!serverKeys.TryGetValue(serverKey, out serverNode))
            {
                throw new InvalidOperationException(string.Format("Could not find server node in server tree with key:{0}", serverKey));
            }
           
            return serverKeys[serverKey];
        }

        /// <summary>
        /// Generates all the keys for the given memcached server.
        /// </summary>
        /// <param name="serverNode">The server.</param>
        /// <param name="serverIndex">Index of the server in the collection of servers.</param>
        private void GenerateKeys(IMemcachedServerNode serverNode, int serverIndex)
        {
            for (int x = 0; x < ServerPermutations; x++)
            {
                byte[] serverKey = Encoding.ASCII.GetBytes(string.Format("{0}:{1}-{2}", serverNode.ServerAddress, serverNode.PortNumber, x));
                
                uint key = new Jenkins96().ComputeHash(serverKey);

                allKeys[x + (serverIndex * ServerPermutations)] = key;
                serverKeys.Add(key, serverNode);
            }
        }
    }
}
